Composite web services make use of the functionality provided by existing web services (which act as component services) and invoke them to achieve a new and/or complex functionality. Various existing systems use partitioning of applications to improve overall system performance and adaptability. The term “partitions” refers to the pieces of composite service specification (or the workflow specification) that get generated after the input composite specification is partitioned by a decentralizing algorithm. Typically these systems aim at minimizing the data on the network or the number of hops.
These two approaches are exemplified by Zhuang and Pande, and Baresi et al., which have the following respective references: X. Zhuang and S. Pande, “Compiler scheduling of mobile agents for minimizing overheads”, In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS '03), May 2003; and, L. Baresi, A. Maurino, and S. Modafferi, “Partitioning of workflows on mobile information systems”, In IFIP TC8 Working Conference on Mobile Information Systems (MOBIS '04), 2004.
Zhuang and Pande show how to schedule mobile agents to optimize either the data on the network or to optimize the number of data transfers. Baresi et al. present an alternate approach for partitioning the execution of BPEL processes on to a network of mobile devices.
For a given set of available resources at runtime, however, the “best” solution is not necessarily the topology with the least number of hops, or the topology that minimizes the data on the network. An alternative approach is to dynamically adapt to runtime changes in available resources. Dynamic reconfiguration of a system is used to improve overall system performance in two existing application partitioning approaches, namely “method partitioning” (Zhou et al.), and “coign” (Hunt and Scott). Zhou et al. and Hunt and Scott have the following references: D. Zhou, S. Pande, and K. Schwan, “Method partitioning—runtime customization of pervasive programs without design-time application knowledge”, In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS '03), May 2003; and, G. Hunt and M. Scott, “The coign automatic distributed partitioning system”, In Proceedings of the 3rd Symposium on Operating System Design and Implementation (OSDI '99), February 1999. The method partitioning and coign models both choose the optimal partitioning plan at run-time, based on monitored data.
Method partitioning uses static analysis to partition methods responsible for message handling. Cost models are used for evaluating the costs/benefits of different partitioning plans. These models are used with data collected from runtime profiling to monitor the actual costs of candidate plans and dynamically select “best” plan from the candidate plans.
Coign is an automatic distributed partitioning system for COM (Component Object Model) components. For an application consisting of distributable COM components, a graph model is constructed of the application's inter-component communication through scenario-based profiling. A graph-cutting algorithm is then used to partition the application across a network, and minimize execution delay due to network communication.
However the models presented in both these papers restrict themselves to partitioning of an application over two nodes. If any resource (such as CPU, memory, or IO) on one of the two nodes or the bandwidth between the two nodes becomes a bottleneck, then not much adaptation can be done. A composite web service will typically consist of more than one component web service (and hence, more than two nodes in the system), and these additional nodes can be used to route messages to one another as long as data and control flow dependencies are respected. This allows makes it possible to adaptively use different links (i.e. topologies) in response to variation in availability of resources like network bandwidth.
There are also various approaches developed in the field of adaptive systems and adaptation frameworks, as described immediately below. These approaches make use of runtime adaptations; however they don't concern themselves with orchestrating applications or services.
Quality Objects (QuO) is a framework for creating CORBA applications that adapt to different Quality of Services (QoS) offered by the underlying network. QuO is described in R. Vanegas, J. Zinky, J. Loyall, D. Karr, R. Schantz, and D. Bakken. “Quo's runtime support for quality of service in distributed objects”, In Middleware '98, 1998. Also, FARA provides a framework of abstractions and mechanisms for building integrated adaptation and resource allocation services in complex real-time systems. FARA is described in D. Rosu, K. Schwan, and S. Yalamanchili, Fara—a framework for adaptive resource allocation in complex real-time systems, In The 4th IEEE Real-Time Technology and Applications Symposium (RTAS), 1998.
MIMO uses multiple-input, multiple-output control theory to control the overall CPU and memory utilization of a system (such as a web server) through the MaxClients and KeepAlive parameters. MIMO is described [8] Y. Diao, N. Gandhi, J. L. Hellerstein, S. Parekh, and D. M. Tilbury. “Using mimo feedback control to enforce policies for interrelated metrics with application to the apache web server”, In Proceedings of the Network Operations and Management Symposium, February 2002.
CANS provides an application-level infrastructure for injecting application-specific components into the network. Dynamic composition of these individual components and distributed adaptation of these components in provided response to system conditions. CANS is described in X. Fu, W. Shi, A. Akkerman, and V. Karamcheti, “Cans: Composable, adaptive network services infrastructure”, In 3rd USENIX Symposium on Internet Technologies and Systems, 2001.
Existing approaches to orchestrating applications or services, such as those examples described above, are not universally satisfactory, and improved approaches are desirable. A need thus exists for such improved approaches, especially approaches suited to orchestrating composite services delivered via a network.